/**
 * Java implementation of Binary Search Tree rotation methods for use in self-
 * balancing trees.
 * 
 * @author Jonathan E. Landrum <me@jonlandrum.com>
 * @since 2016-01-15
 */

package com.jonlandrum.selfbalancingtree;

public class SelfBalancingTree<T extends Comparable<T>> extends BinarySearchTree<T> {
    /*
     * Constructors
     */
    public SelfBalancingTree() {
        super();
    }
    
    public SelfBalancingTree(T d) {
        super(d);
    }
    
    public SelfBalancingTree(Node<T> n) {
        super(n);
    }
    
    /*
     * Operations
     */
    protected void rotateLeft(Node<T> n) {
        if (!n.hasRightChild()) {
            return;
        } else {
            if (n.isRoot()) {
                root = n.getRightChild();
                root.setParent(null);
                if (root.hasLeftChild()) {
                    n.setRightChild(root.getLeftChild());
                    n.getRightChild().setParent(n);
                } else {
                    n.setRightChild(null);
                }
                root.setLeftChild(n);
                n.setParent(root);
            } else {
                if (n.isLeftChild()) {
                    n.getParent().setLeftChild(n.getRightChild());
                    n.getRightChild().setParent(n.getParent());
                    if (n.getRightChild().hasLeftChild()) {
                        n.setRightChild(n.getRightChild().getLeftChild());
                        n.getRightChild().setParent(n);
                    } else {
                        n.setRightChild(null);
                    }
                    n.getParent().getLeftChild().setLeftChild(n);
                    n.setParent(n.getParent().getLeftChild());
                } else {
                    n.getParent().setRightChild(n.getRightChild());
                    n.getRightChild().setParent(n.getParent());
                    if (n.getRightChild().hasLeftChild()) {
                        n.setRightChild(n.getRightChild().getLeftChild());
                        n.getRightChild().setParent(n);
                    } else {
                        n.setRightChild(null);
                    }
                    n.getParent().getRightChild().setLeftChild(n);
                    n.setParent(n.getParent().getRightChild());
                }
            }
        }
    }
    
    protected void rotateRight(Node<T> n) {
        if (!n.hasLeftChild()) {
            return;
        } else {
            if (n.isRoot()) {
                root = n.getLeftChild();
                root.setParent(null);
                if (root.hasRightChild()) {
                    n.setLeftChild(root.getRightChild());
                    n.getLeftChild().setParent(n);
                } else {
                    n.setLeftChild(null);
                }
                root.setRightChild(n);
                n.setParent(root);
            } else {
                if (n.isLeftChild()) {
                    n.getParent().setLeftChild(n.getLeftChild());
                    n.getLeftChild().setParent(n.getParent());
                    if (n.getLeftChild().hasRightChild()) {
                        n.setLeftChild(n.getLeftChild().getRightChild());
                        n.getLeftChild().setParent(n);
                    } else {
                        n.setLeftChild(null);
                    }
                    n.getParent().getLeftChild().setRightChild(n);
                    n.setParent(n.getParent().getLeftChild());
                } else {
                    n.getParent().setRightChild(n.getLeftChild());
                    n.getLeftChild().setParent(n.getParent());
                    if (n.getLeftChild().hasRightChild()) {
                        n.setLeftChild(n.getLeftChild().getRightChild());
                        n.getLeftChild().setParent(n);
                    } else {
                        n.setLeftChild(null);
                    }
                    n.getParent().getRightChild().setRightChild(n);
                    n.setParent(n.getParent().getRightChild());
                }
            }
        }
    }
}